package com.example.binarytree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jonathan
 * 2021/4/15 21:57
 * 都是负数 怎么判断？
 */
public class MaxSumBST {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List<Integer> list = new ArrayList<>();

    public int maxSumBST(TreeNode root) {
        boolean isAllMinus = true;
        for (Integer integer : list) {
            if (integer >= 0) {
                isAllMinus = false;
                break;
            }
        }
        return isAllMinus ? 0 : process(root).maxSum;
    }


    public static class Info {
        public boolean isAllBST;
        public int maxSubBSTSize;
        public int maxSum;
        public int min;
        public int max;

        public Info(boolean isAllBST, int maxSubBSTSize, int maxSum, int min, int max) {
            this.isAllBST = isAllBST;
            this.maxSubBSTSize = maxSubBSTSize;
            this.maxSum = maxSum;
            this.min = min;
            this.max = max;
        }
    }

    private TreeNode root;

    private Info process(TreeNode x) {
        if (x == null) {
            return null;
        }
        list.add(x.val);
        //左子树
        Info left = process(x.left);
        Info right = process(x.right);


        int min = x.val;
        int max = x.val;
        int maxSum = x.val;
        if (left != null) {
            min = Math.min(min, left.min);
            max = Math.max(max, left.max);
            maxSum = left.maxSum;
        }

        if (right != null) {
            min = Math.min(min, right.min);
            max = Math.max(max, right.max);
            maxSum = Math.max(maxSum, right.maxSum);
        }

        boolean isAllBST = false;
        // 情况一 与x无关的情况 不是左边就是右边
        int maxSubBSTSize = 0;
        if (left != null) {
            maxSubBSTSize = left.maxSubBSTSize;
        }
        if (right != null) {
            maxSubBSTSize = Math.max(maxSubBSTSize, right.maxSubBSTSize);
        }
        //情况二 与x有关
        // 左树是二叉搜索树
        if ((left == null ? true : left.isAllBST)
                && (right == null ? true : right.isAllBST)
                && (left == null ? true : left.max < x.val)
                && (right == null ? true : x.val < right.min)
        ) {
            maxSubBSTSize = (left == null ? 0 : left.maxSubBSTSize) + (right == null ? 0 : right.maxSubBSTSize) + 1;
            isAllBST = true;
            maxSum = (left == null ? 0 : left.maxSum) + (right == null ? 0 : right.maxSum) + x.val;
        }
        return new Info(isAllBST, maxSubBSTSize, maxSum, min, max);
    }

    public void add(int[] nums) {
        for (int e : nums) {
            root = add(root, e);
        }

    }

    private TreeNode add(TreeNode x, Integer e) {
        if (x == null) {
            return new TreeNode(e);
        }
        if (e < x.val) {
            x.left = new TreeNode(e);
        } else if (e > x.val) {
            x.right = new TreeNode(e);
        }
        return x;
    }


    public static void main(String[] args) {
        MaxSumBST bst = new MaxSumBST();
        bst.add(new int[]{});

    }


}
